\section{Related work}
\label{sec:token.relatedwork}

Information spreading (or dissemination) in networks is one of the
most basic problems in computing and has a rich literature. The
problem is generally well-understood on static networks, both for
interconnection networks~\cite{leighton:book} as well as general
networks~\cite{lynch:distributed,attiya+w:distributed}.  In
particular, the $k$-gossip problem can be solved in $O(n + k)$ rounds
on any $n$-static network~\cite{topkis:disseminate}.  There also have
been several papers on broadcasting, multicasting, and related
problems in static heterogeneous and wireless networks (e.g.,
see~\cite{alon+blp:radio,bar-yehuda+gi:radio,bar-noy+gns:multicast,clementi+ms:radio}).

Dynamic networks have been studied extensively over the past three
decades.  Some of the early studies focused on dynamics that arise out
of faults, i.e., when edges or nodes fail.  A number of fault models,
varying according to extent and nature (e.g., probabilistic
vs. worst-case) and the resulting dynamic networks have been analyzed
(e.g., see~\cite{attiya+w:distributed,lynch:distributed}).  There have
been several studies on models that constrain the rate at which
changes occur, or assume that the network eventually stabilizes (e.g.,
see~\cite{afek+ag:dynamic,dolev:stabilize,gafni+b:link-reversal}).

There also has been considerable work on general dynamic networks.
Some of the earliest studies in this area
include~\cite{afek+gr:slide,awerbuch+pps:dynamic} which introduce
general building blocks for communication protocols on dynamic
networks. Another notable work is the local balancing approach
of~\cite{awerbuch+l:flow} for solving routing and multicommodity flow
problems on dynamic networks.  Algorithms based on the local balancing
approach continually balance the packet queues across each edge of the
network and drain packets that have reached their destination. The
local balancing approach has been applied to achieve near-optimal
throughput for multicast, anycast, and broadcast problems on dynamic
networks as well as for mobile ad hoc
networks~\cite{awerbuch+bbs:route,awerbuch+bs:anycast,jia+rs:adhoc}.

Modeling general dynamic networks has gained renewed attention with
the recent advent of heterogeneous networks composed out of ad hoc,
and mobile devices.  To address the unpredictable and often unknown
nature of network dynamics,~\cite{kuhn+lo:dynamic} introduce a model
in which the communication graph can change completely from one round
to another, with the only constraint being that the network is
connected at each round.  The model of~\cite{kuhn+lo:dynamic} allows
for a much stronger adversary than the ones considered in past work on
general dynamic
networks~\cite{awerbuch+l:flow,awerbuch+bbs:route,awerbuch+bs:anycast}.
In addition to results on the $k$-gossip problem that we have
discussed earlier,~\cite{kuhn+lo:dynamic} consider the related problem
of counting, and generalize their results to the $T$-interval
connectivity model, which includes an additional constraint that any
interval of $T$ rounds has a stable connected spanning subgraph.  The
survey of~\cite{kuhn-survey} summarizes recent work on dynamic
networks.

We note that the model of~\cite{kuhn+lo:dynamic}, as well as ours,
allow only edge changes from round to round while the nodes remain
fixed. Recently, the work of \cite{p2p-soda} introduced a dynamic
network model (motivated by P2P networks) where both nodes and edges
can change by a large amount (up to a linear fraction of the network
size). They show that stable amost-everywhere agreement can be
efficiently solved in such networks even in adversarial dynamic
settings. 

Recent work of~\cite{haeupler:gossip,haeupler+k:dynamic} presents
information spreading algorithms based on network
coding~\cite{ahlswede+cly:coding}.  As mentioned earlier, one of their
important results is that the $k$-gossip problem on the adversarial
model of~\cite{kuhn+lo:dynamic} can be solved using network coding in
$O(n+k)$ rounds assuming the token sizes are sufficiently large
($\Omega(n\log n)$ bits). For further references to using network
coding for gossip and related problems, we refer to the recent works
of
~\cite{haeupler:gossip,haeupler+k:dynamic,avin1,avin2,deb+mc:coding,shah}
and the references therein.

Our offline approximation algorithm makes use of results on the
Steiner tree packing problem for directed
graphs~\cite{cheriyan+s:steiner}.  This problem is closely related to
the directed Steiner tree problem (a major open problem in
approximation
algorithms)~\cite{charikar+ccdgg:steiner,zosin+k:steiner} and the gap
between network coding and flow-based solutions for multicast in
arbitrary directed networks~\cite{agarwal+c:coding,sanders+et:flow}.

Finally, we note that there are also a number of studies that solve
$k$-gossip and related problems using {\em gossip-based} processes.
In a local gossip-based algorithm, each node exchanges information
with a small number of randomly chosen neighbors in each round.
Gossip-based processes have recently received significant attention
because of their simplicity of implementation, scalability to large
network size, and their use in aggregate computations,
e.g.,~\cite{berenbrink+ceg:gossip,demers,kempe,chen-spaa,karp,shah,boyd}
and the references therein.  All these studies assume an underlying
static communication network, and do not apply directly to the models
considered in this paper.  A related recent work on dynamic networks
is~\cite{avin+kl:dynamic} which analyzes the cover time of random
walks on dynamic networks. 
